# -*- coding: utf-8 -*-

"""剑指 Offer II 018. 有效的回文
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。

示例 1:
输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:
输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串

提示：
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成"""


class Solution:
    """双指针好用，由于限定了字母和数字字符，可以建表用查表法比较，同时也就可以将大小写忽略一并在表中做值统一"""
    def isPalindrome(self, s: str) -> bool:
        table = {}
        for n in range(65, 90+1):
            table[chr(n)] = n-64
        for n in range(97, 122+1):
            table[chr(n)] = n-96
        for n in range(48, 57+1):
            table[chr(n)] = n

        head, tail = 0, len(s)-1
        ispalin, isbreak = True, False
        try:
            while True:
                while True:
                    hv = table.get(s[head], 0)
                    if hv:
                        break
                    else:
                        head += 1
                
                while True:
                    tv = table.get(s[tail], 0)
                    if tv:
                        break
                    else:
                        tail -= 1

                if hv == tv:
                    head += 1
                    tail -= 1
                    ispalin = True
                else:
                    ispalin = False
                    isbreak = True

                if tail-head in (0, -1):
                    isbreak = True
                
                if isbreak:
                    break
        except IndexError:
            pass

        return ispalin


if __name__ == '__main__':
    so = Solution()
    print(so.isPalindrome('A man, a plan, a canal: Panama'))
    print(so.isPalindrome('race a car'))
    print(so.isPalindrome('refer'))
    print(so.isPalindrome(' ,: '))

